/**
 * 八皇后
 * Created by MGL on 2017/2/23.
 */
public class EightQueens01 {
    public static void main(String[] args) {
        EightQueens01 eightQueens01 = new EightQueens01();
        eightQueens01.search();
    }

    /**
     * 初始化
     */
    public void search() {
        //横向同一栏是否有皇后，1表示有
        int[] column = new int[9];
        //右上至左下是否有皇后
        int[] rup = new int[17];
        //左上至右下是否有皇后
        int[] lup = new int[17];
        //储存保存的皇后的位置（如queen[1] = 3）
        //代表在第一行的第三个位置有个皇后
        int[] queen = new int[9];
        System.out.println(search(1, column, rup, lup, queen, 0));
    }

    /**
     * 进行查找
     * @param i 第几行
     * @param column  横向同一栏是否有皇后，1表示有
     * @param rup 右上至左下是否有皇后
     * @param lup 左上至右下是否有皇后
     * @param queen 答案
     * @param count 当前解的个数
     * @return
     */
    private int search(int i, int[] column, int[] rup, int[] lup, int[] queen, int count) {
        if (i > 8) {
            return show(count, queen);
        } else {
            for (int j = 1; j <= 8; j++) {
                //判断同一横栏是否有皇后    判断右上至左下是否有皇后   判断左上至右下是否有皇后
                if ((column[j] == 0) && (rup[i + j] == 0) && (lup[i - j + 8] == 0)) {
                    //保存结果
                    queen[i] = j;
                    column[j] = rup[i + j] = lup[i - j + 8] = 1;
                    //跳到下一行继续探索
                    count = search(i + 1, column, rup, lup, queen, count);
                    column[j] = rup[i + j] = lup[i - j + 8] = 0;
                }
            }
        }
        return count;
    }

    /**
     * 打印皇后结果
     * @param count
     * @param queen
     * @return
     */
    private int show(int count, int[] queen) {
        count++;
        System.out.println("\n解答" + count);
        for (int y = 1; y <= 8; y++) {
            for (int x = 1; x <= 8; x++) {
                if (queen[y] == x) {
                    System.out.print("Q");
                } else {
                    System.out.print(".");
                }
            }
            System.out.print("\n");
        }
        return count;
    }
}
